package models;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import android.text.format.Time;
import android.util.Log;

public class ScheduleMaker {
	
	/**
	 * Generates a schedule from a map of long to tasks, a day start time, and a day end time.
	 * Assumes no overlap in tasks with predefined start times.  Assumes there is enough time to travel to a task before it schedules a start time, and enough time for the task
	 * to last duration in length before starting to travel to the next task.  startTime and endTime must follow this as well (see parameter description).
	 * The time a task takes looks like ((end time of previoius task -->)| -travel time to task- | (<--start time of task) -duration- | (<--point to start next tasks travel)
	 * Failure to meet these prerequisites has undefined results (so don't do it).
	 * Any tasks that don't fit between the start time and end time will be left out of the final schedule.  If startTime is later than endTime (looks at hours and days only), it will be
	 * assumed that startTime is meant to be the previous day.  The startTime and endTime must not be the same time.  0 duration tasks will possibly be left out of a schedule.
	 * On failure to find a suitable schedule, returns a schedule that has less Task objects in it than were in tasks.  This shorter
	 * schedule is the best way (by our metric) to do the most tasks.
	 * 
	 * @param tasksOriginal a collection containing the tasks to schedule
	 * @param startTime the earliest the schedule day should start.  Must be no later than the duration of travel time earlier
	 * than the first scheduled task time. ( startTime--> | -travel time- | <-- start time of first task )
	 * @param endTime the latest a task should be scheduled.  Must be no earlier than the duration of the last scheduled task later than the start time
	 * of the last task ( start time of last task --> | -last task duration- | <-- endTime )
	 * @return newly generated schedule
	 */
	public static Schedule generateSchedule(Collection<Task> tasksOriginal, Time startTime, Time endTime) { // change to collection
		//Collection<Task> tasks = new HashSet<Task>();
		//tasks.addAll(tasksOriginal);
		startTime = normalizeTime(startTime);
		endTime = normalizeTime(endTime);
		if (startTime.toMillis(false) > endTime.toMillis(false)) {
		    endTime.monthDay++;
		}
		Collection<Task> tasks = copyAndNormalize(tasksOriginal);
		Map<Long, Task> tasksMap = new HashMap<Long, Task>();
		for (Task t : tasks) {
		    tasksMap.put(t.getID(), t);
		}
		Map<Long, Task> scheduledTasks = new HashMap<Long, Task>(); // map to feed into schedule constructor		
		List<TimeSortingWrapper> boundaryTimes = new ArrayList<TimeSortingWrapper>();// holds the boundary times, mapped by start (taskstart - driving time)
		
		// Add startTime and endTime to the list of boundary times to consider, need wrapper to be sortable
		boundaryTimes.add(new TimeSortingWrapper(startTime));
		boundaryTimes.add(new TimeSortingWrapper(endTime));
		
		// separate tasks between set start times and not
		for (Task tO : tasksOriginal) { // was concurrent modification
		    Task t = tasksMap.get(tO.getID());
			Time taskStartTime = t.getStartTime();
			if (taskStartTime == null) { //
				// do nothing
			} else {
			    if (taskStartTime.toMillis(false) < startTime.toMillis(false)) {
			        taskStartTime.monthDay++;
			    }
				tasks.remove(t);
				if (taskStartTime.toMillis(false) - t.getEstimatedTravel() >= startTime.toMillis(false) 
				        && taskStartTime.toMillis(false) + t.getEstimatedDuration()
				            <= endTime.toMillis(false)) {
				    scheduledTasks.put(t.getID(), t);
                    Time startBoundary = createEarlierTime(taskStartTime, (int) t.getEstimatedTravel());
                    Time endBoundary = createLaterTime(taskStartTime, (int) t.getEstimatedDuration());
                    
                    boundaryTimes.add(new TimeSortingWrapper(startBoundary));
                    boundaryTimes.add(new TimeSortingWrapper(endBoundary));
				}
			}
		}
		assert(boundaryTimes.size() % 2 == 0);
		// get boundaries in order
		Collections.sort(boundaryTimes);
		

		// for each "partition" in the schedule, run knapsack to fill schedule.
		for (int i = 0; i < boundaryTimes.size() / 2; i++) {
			TimeSortingWrapper first = boundaryTimes.get(2 * i);
			TimeSortingWrapper second = boundaryTimes.get(2 * i + 1);
			Log.v("first", first.time.toString());
			Log.v("second", second.time.toString());
			
			int duration = first.difference(second);
			Log.v("tasksLength", "" + tasks.size());
			Collection<Task> tasksForThisPortion = knapsackSolver(tasks, duration);
			Log.v("tasksForThisPortionLength", "" + tasksForThisPortion.size());
			
			// remove the tasks for this part of the schedule from all tasks, so no duplicates arise
			for (Task task : tasksForThisPortion) {
				tasks.remove(task); // modify task
			}
			
			assignStartTimes(first.time, tasksForThisPortion);
			
			for (Task task : tasksForThisPortion) {
				Log.v("right before added to schedule", task.getStartTime().toString());
				scheduledTasks.put(task.getID(), task);
				Log.v("task id", "" + task.getID());
			}
		}
		// debug
		for (Task task : scheduledTasks.values()) {
			Log.v("task at end time", task.getStartTime().toString());
		}
		
		return new Schedule(scheduledTasks, startTime, endTime);
		
	}
	
	// modifies tasks.  Starting at time startboundary, assigns start times to tasks, packing them as tightly
	// as possible in no particular order.  Allows driving time before assigned start time.
	private static void assignStartTimes(Time startBoundary, Collection<Task> tasks) {
		Time nextBoundary = startBoundary;
		Log.v("nextBoundary", nextBoundary.toString());
		for (Task task : tasks) {
			Log.v("estimated time", "" + task.getEstimatedTravel());
			Time startTime = createLaterTime(nextBoundary, (int) task.getEstimatedTravel());
			Log.v("startTime", startTime.toString());
			task.setStartTime(startTime);
			// update next time
			Log.v("extimated duration", "" + task.getEstimatedDuration());
			nextBoundary = createLaterTime(startTime, (int) task.getEstimatedDuration());
			Log.v("new next boundary", nextBoundary.toString());
		}
	}
	
	// Solve knapsack problem
	private static Collection<Task> knapsackSolver(Collection<Task> tasks, int duration) {
		assert(tasks != null);
		int n = tasks.size();
		Map<Integer, Task> taskMap = new HashMap<Integer, Task>(); // ignore 0th index for now, easier to follow psuedocode
		int[] weights = new int[n + 1];
		int[] values = new int[n + 1];
		Log.d("n = ", n + "--");
		Log.d("duration = ", duration + "--");
		int[][] opt = new int[n + 1][duration + 1];
		
		// Extract out relevant information and map to simple numbered index
		int index = 1;
		for (Task task : tasks) {
			taskMap.put(index, task);
			weights[index] = (int) task.getEstimatedDuration();
			values[index] = weights[index] * (task.getPriority() + 1); // time duration times priority gives the "value" for scheduling...balanced?
			index++;
		}
		
		for (int w = 0; w < duration; w++) { // may be unnecessary, initialized to 0?
			opt[0][w] = 0;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int w = 0; w <= duration; w++) {
				if (weights[i] > w) {
					opt[i][w] = opt[i-1][w];
				} else {
					opt[i][w] = Math.max(opt[i - 1][w], opt[i - 1][w - weights[i]] + values[i]);
				}
			}
		}
		
		boolean[] isIncluded = new boolean[n + 1];
		extractSolution(opt, values, weights, isIncluded, n, duration);
		
		// create set of tasks that were included
		Set<Task> results = new HashSet<Task>();
		Log.v("included ", Arrays.toString(isIncluded));
		for (int i = 1; i <= n; i++) {
			
			if (isIncluded[i]) {
				results.add(taskMap.get(i));
			}
		}
		return results;
	}
	
	// extracts solutions from completed opt table, with given values, weights.  i and w should be duration and total weight.  result is modified.
	private static void extractSolution(int[][] opt, int[] values, int[] weights, boolean[] result, int i, int w) {
		assert(opt != null);
		assert(result != null);
		if (i == 0 || w == 0) {
			// do nothing
		} else if (opt[i][w] == opt[i - 1][w]) {
			extractSolution(opt, values, weights, result, i - 1, w);
		} else {
			assert(opt[i][w] == opt[i - 1][w - weights[i]] + values[i]);
			result[i] = true;
			extractSolution(opt, values, weights, result, i - 1, w - weights[i]);
		}
	}
	
	// returns a new Time object that is duration earlier than t
	private static Time createEarlierTime(Time t, int duration) {
		/*Time result = new Time(t);
		int mins = duration % 60;
		int hours = duration / 60;
		result.minute = result.minute - mins;
		result.hour -= hours; // this could create a negative hour on boundary case...check with later.
		if (result.minute < 0) {
			result.minute += 60;
			result.hour -= 1;
		}
		if (result.hour < 0) {
			result.monthDay--;
			result.hour = result.hour + 24;
		}
		return result;*/
		Log.v("Creating earlier time", "" + t.toString());
		long millis = t.toMillis(false);
		Log.v("millis", "" + millis);
		Time result = new Time();
		result.set(millis - duration * 60000);
		Log.v("earlier time created:", "" + result.toString());
		return result;
	}
	
	// returns a new Time object that is duration later than t - possibly combine with createEarlierTime later
	private static Time createLaterTime(Time t, int duration) {
		/*Time result = new Time(t);
		int mins = duration % 60;
		int hours = duration / 60;
		result.hour += hours + (result.minute + mins) / 60; // doesn't overlap till next day..25 hours?
		result.minute = (result.minute + mins) % 60;
		
		return result;*/
		Log.v("Creating later time", "" + t.toString());
		long millis = t.toMillis(false);
		Time result = new Time();
		result.set(millis + (duration * 60000));
		Log.v("Later time created:", "" + result.toString());
		return result;
	}
	
	// Sets all times in tasks to valid dates
	private static Collection<Task> copyAndNormalize(Collection<Task> tasks) {
		Log.v("normalizeTimes", "normlizing times");
		Collection<Task> results = new HashSet<Task>();
		for (Task t : tasks) {
			Log.v("start loop", "blah");
			Time time = null;
			if (t.getStartTime() != null) {
				time = normalizeTime(t.getStartTime());
			}
			Task nt = new Task(t.getID(), t.getTitle(), time, t.getEstimatedDuration(), t.getEstimatedTravel(), t.getPriority(), t.isCompleted());
			results.add(nt);
		}
		Log.v("done normalizing times", "done normalizing times");
		return results;
	}
	
	// Sets the given time to a valid date
	private static Time normalizeTime(Time time) {
		Time result = new Time();
		result.monthDay = 12;
		result.year = 1986;
		result.month = 9;
		result.hour = time.hour;
		result.minute = time.minute;
		return result;
	}
}